class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        # n 是棋盘大小
        # k 是走的步数
        # row 是行，column 是列
        directions = [(1, -2), (1, 2), (-1, -2), (-1, 2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
        chess_loc = [row, column]

        # 只有基本数据类型是拷贝值，其他都是拷贝地址
        dp = [[[0] * n for _ in range(n)] for _ in range(k+1)] 
        
        for step in range(k+1):
            for x in range(n):
                for y in range(n):
                    if step == 0:
                        dp[step][x][y] = 1
                    else:
                        for dx, dy in directions:
                            x_p, y_p = x+dx, y+dy
                            if 0 <= x_p < n and 0 <= y_p < n:
                                dp[step][x][y] += dp[step-1][x_p][y_p]/8
        
        # 对于马而言，其动作都是可逆转的
        # 因此原问题等同于：马能从哪里跳到当前位置。
        return dp[step][row][column]

if __name__ == '__main__':
    s = Solution()
    print(s.knightProbability(n = 3, k = 2, row = 0, column = 0))
    print(s.knightProbability(n = 1, k = 0, row = 0, column = 0))
    print(s.knightProbability(n = 7, k = 5, row = 4, column = 4))
    